#include <vector>
#include <deque>
#include <list>
#include <iostream>

namespace std {
	template <class T> 
	class MyAllocator
	{
	public:
		typedef typename T value_type; // the type that the allocator manages.
		typedef value_type *pointer;
		typedef value_type& reference;
		typedef const value_type *const_pointer;
		typedef const value_type& const_reference;

		typedef ptrdiff_t difference_type;
		typedef size_t size_type;

	template<class U>
		struct rebind {	// convert this type to allocator<U>
			typedef MyAllocator<U> other;
		};

		MyAllocator() { /* creates a default instance of X */ }
		
		MyAllocator(const MyAllocator<T>& a) {
			// the copy compares equal to a
			// this is the case anyway, because all members depend on the value_type, which is the same
		}

		bool MyAllocator::operator==(const MyAllocator &other) const {
			// Returns true if ond only if storage allocated using a can be deallocated using b, and vice versa.
			return value_type == other.value_type;
		}

	template<class U>
		MyAllocator(const MyAllocator<U>& y)
		{	
			/* creates a copy of y, an Allocator whose value type is U.
			Postcondition: Y(X(y)) == y */
		}

		pointer allocate(size_type n)
		{
			//Allocates n*sizeof(T) bytes of memory. (0<n<=a.max_size())
			//return value is a pointer to an uninitialized block of 
			//memory that is large enough to contain n objects of type T
			void* ptr = ::operator new(n*sizeof(T));

			return (pointer) ptr; //need to cast to pointer type
		}

		pointer allocate(size_type n, const void* q)
		{
			//allocates n*sizeof(T) bytes of memory. the pointer  is a hint. 
			//An allocator might use it as an aid to locality. or it might 
			//ignore the hint entirely.
			
			//return value is a pointer to an uninitialized block of 
			//memory that is large enough to contain n objects of type T

			return allocate(n); //hint is ignored entirely
		}

		void deallocate(pointer p, size_type n)
		{
			//deallocates the memory that p points to
			delete(p);
		}

		size_type max_size() const
		{
			//returns the maximum value that can be passed as an argument to allocate
			return (size_type)(-1) / sizeof (T); //cast -1 to unsigned value, gets largest possible value. divide by size of T to get maximum array size
		}

		void construct(pointer p, const T& t)
		{
			// p points to an uninitialized region of memory whose size is at least sizeof(T).
			// equivalent to new((void*) p) T(t);
			new( (void*) p ) T(t); //this will not work if regular new operator of T is overloaded
		}

		void destroy(pointer p)
		{
			// p points to an object of type T.
			//equivalent to ((T*) p)->~T(); //destructor

			((T*) p)->~T(); //destructs object of type T at p
		}

		pointer address(reference r) const
		{	
			//return address of mutable r
			return ((pointer) &(char&)r);
		}

		const_pointer address(const_reference r) const
		{
			// return address of nonmutable r
			return ((const_pointer) &(char&)r);
		}

	template<class U>
		MyAllocator<T>& operator=(const MyAllocator<U>&)
		{	
			// assign from a related allocator (do nothing)
			return (*this);
		};

	};
};

class BaseClass
{

public:
	short member;
	BaseClass()
	{
		member = 0xff;
	}

	BaseClass(short _m)
	{
		member=_m;
	}

	BaseClass(const BaseClass& other)
	{
		member=other.member;
	}

	//implementing new(size_t) will lead to a compiler error, because new(size_t, void*) is required.

	virtual ~BaseClass()
	{
		printf("Destruktor\n");
	}
};

//used to quickly switch between containers
typedef std::list<BaseClass, std::MyAllocator<BaseClass>> container_type;

int main(int argc, char* argv)
{
	container_type v;
	v.push_back(BaseClass(1));
	v.push_back(BaseClass(2));
	v.push_back(BaseClass(3));

	//iterate through container and output each value
	for(container_type::iterator I = v.begin(); I != v.end(); ++I)
	{
		std::cout << I->member << std::endl;
	}

	v.clear(); //remove objects from container
	
	return 0;
}